package com.example.demo.arithmetic.hash;

import java.util.HashMap;
import java.util.Map;

public class Leetcode {
    public static void main(String[] args) {
//        new Leetcode().lengthOfLongestSubstring("abcabcbb");
        new Leetcode().lengthOfLongestSubstring("abba");
    }

    /**
     * 最长字串
     * 1.begin end分别表示字串开始和结束位置
     * 2.用hash表检查重复字符
     * 3.从左向右查看每个字符，如果
     * -没遇到重复字符，调整end
     * -遇到重复字符，调整begin
     * -将当前字符放入hash表
     * 4.end-begin+1是当前字串长度
     * <p>
     * abcabcbb
     * <p>
     * 3
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int begin = 0;
        int maxLength = 0;
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                begin = Math.max(begin, map.get(ch) + 1);
                map.put(ch, end);
            } else {
                map.put(ch, end);
            }
            System.out.println(s.substring(begin, end + 1));
            maxLength = Math.max(maxLength, end - begin + 1);
        }

        return maxLength;
    }
}
